package com.fmm.medium;

public class CleverThief {

    /**
     * @param num 街区数组，其中的元素代表家里的金额
     * @return 最大偷窃金额
     */
    public static int maxStolenMoney(int[] num) {
        // 创建动态规划数组，其中 dp[k] 表示前 k+1 所房子的最佳利益
        int[] dp = new int[num.length];
        for (int i = 0; i < num.length; i++) {
            // 边界值，只有一所房子时，最佳为这所房子的金额
            if (i == 0) {
                dp[i] = num[i];
            } else if (i == 1) {
                // 只有两所房子时，最佳为两所房子中金额较大的
                dp[i] = Math.max(num[i], num[i - 1]);
            } else {
                // 否则，最佳为前一所房子的最佳收益 和 (前两所房子最佳收益 + 本所房子的金额) 中较大的
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + num[i]);
            }
        }
        return dp[num.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(maxStolenMoney(new int[]{1}));
        System.out.println(maxStolenMoney(new int[]{1, 4}));
        System.out.println(maxStolenMoney(new int[]{1, 4, 2}));
        System.out.println(maxStolenMoney(new int[]{1, 4, 2, 3}));
        System.out.println(maxStolenMoney(new int[]{1, 4, 2, 3, 4}));
        System.out.println(maxStolenMoney(new int[]{1, 4, 2, 3, 4, 1}));
        System.out.println(maxStolenMoney(new int[]{1, 4, 2, 3, 4, 1, 2}));
    }
}
